package com.ztom.top100;

/**
 * 最长回文子序列
 * <p>
 * https://leetcode-cn.com/problems/longest-palindromic-subsequence/
 *
 * @author ZhangTao
 */
public class Code71LongestPalindromeSubseq {

    public int longestPalindromeSubseq1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process(str, 0, str.length - 1);
    }

    // 范围尝试模型
    private int process(char[] str, int l, int r) {
        if (l == r) {
            // 只有一个字符
            return 1;
        }
        if (l == r - 1) {
            // 只有两个字符
            return str[l] == str[r] ? 2 : 1;
        }
        // 既不以 l 开头, 也不以 r 结尾
        int p1 = process(str, l + 1, r - 1);
        // 以 l 开头, 不以 r 结尾
        int p2 = process(str, l, r - 1);
        // 不以 l 开头, 以 r 结尾
        int p3 = process(str, l + 1, r);
        // 既以 l 开头, 又以 r 结尾
        int p4 = str[l] == str[r] ? (2 + process(str, l + 1, r - 1)) : 0;
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }

    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int n = str.length;
        int[][] dp = new int[n][n];
        // 对角线为 1
        dp[n - 1][n - 1] = 1;
        for (int i = 0; i < n - 1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        for (int l = n - 3; l >= 0; l--) {
            for (int r = l + 2; r < n; r++) {
                dp[l][r] = Math.max(dp[l][r - 1], dp[l + 1][r]);
                if (str[l] == str[r]) {
                    dp[l][r] = Math.max(dp[l][r], dp[l + 1][r - 1] + 2);
                }
            }
        }
        return dp[0][n - 1];
    }
}
